
//1475.商品折扣后的最终价格
class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        //从左向右,栈中记录还没有找到满足条件的数据
        int n=prices.size();
        stack<pair<int,int>> st;
        st.push({prices[0],0});
 
        vector<int> ret(prices);   //没有折扣的位置就是原价
        for(int i=1;i<n;i++)
        {
            while(!st.empty()&&st.top().first>=prices[i]) //将找到答案的出栈
            {
                int index=st.top().second;
                ret[index]=st.top().first-prices[i];
                st.pop();
            }

            st.push({prices[i],i});  //当前位置入栈
        }
        return ret;
    }
};